package com.ljy.my_study.leetcode.通过删除字母匹配到字典里最长单词;

import java.util.List;

/**
 * @author lijunying
 * @date 2021/9/14 9:05
 */
public class TestMain {

//    给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
//
//    如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
//
//             
//
//    示例 1：
//
//    输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
//    输出："apple"
//    示例 2：
//
//    输入：s = "abpcplea", dictionary = ["a","b","c"]
//    输出："a"
//             
//
//    提示：
//
//            1 <= s.length <= 1000
//            1 <= dictionary.length <= 1000
//            1 <= dictionary[i].length <= 1000
//    s 和 dictionary[i] 仅由小写英文字母组成
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {

    }

//    逐一比较dictionary中元素与s，看s是否按顺序包含dictionary中元素
    public String findLongestWord(String s, List<String> dictionary) {
        String result="";
        for(String d:dictionary){
            if(isSubString(s,d)){
                if(d.length()>result.length()){
                    result=d;
                }else if(d.length()==result.length()&&d.compareTo(result)<0){
                    result=d;
                }
            }
        }
        return result;
    }

    private boolean isSubString(String s,String d){
        int sLen=s.length();
        int dLen=d.length();
        if(sLen<dLen){
            return false;
        }
        int sIndex=0;
        int dIndex=0;
        while(sIndex<sLen&&dIndex<dLen){
            if(s.charAt(sIndex)==d.charAt(dIndex)){
                dIndex++;
            }
            sIndex++;
        }
        return dIndex==dLen;
    }
}
